/* 
 * Convert Sorted List to Binary Search Tree
 */

#include "../../func.h"

TreeNode *sortedListToBST(ListNode *head, int len)
{
    if (0 == len)
        return nullptr;
    if (1 == len)
        return new TreeNode(head->val);

    TreeNode *root = new TreeNode(nth_node(head, len / 2 + 1)->val);
    root->left = sortedListToBST(head, len / 2);
    root->right = sortedListToBST(nth_node(head, len / 2 + 2), (len - 1) / 2);
    return root;
}

int listLength(ListNode *node)
{
    int n = 0;

    while (node)
    {
        ++n;
        node = node->next;
    }
    return n;
}
ListNode *nth_node(ListNode *node, int n)
{
    while (--n)
        node = node->next;
    return node;
}